package com.yun.algorithm.backtracking.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class leetcode51 {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();
        boolean[] ca = new boolean[n];//列冲突
        boolean[] cb = new boolean[2 * n - 1];//左斜线冲突
        //i+j
        boolean[] cc = new boolean[2 * n - 1];//右斜线冲突
        //n-1-(i-j)
        char[][] table = new char[n][n];//'.' 'Q'
        for (char[] t : table) {
            Arrays.fill(t, '.');
        }
        dfs(0, n, table, ca, cb, cc, result);
        return result;
    }

    private void dfs(int i, int n, char[][] table,
                     boolean[] ca,
                     boolean[] cb,
                     boolean[] cc,
                     List<List<String>> result) {
        if (i == n) {
            List<String> lists = new ArrayList<>();
            for (char[] t : table) {
                lists.add(new String(t));
            }
            result.add(lists);
        }
        for (int j = 0; j < n; j++) {
            if (ca[j] || cb[i + j] || cc[n - 1 - (i - j)]) {
                continue;
            }
            table[i][j] = 'Q';
            ca[j] = cb[i + j] = cc[n - 1 - (i - j)] = true;
            dfs(i + 1, n, table, ca, cb, cc, result);
            ca[j] = cb[i + j] = cc[n - 1 - (i - j)] = false;
            table[i][j] = '.';
        }
    }

    public static void main(String[] args) {
        int n = 4;
        List<List<String>> result = new leetcode51().solveNQueens(n);
        for (List<String> list : result) {
            System.out.println(list);
        }
    }
}
